package org.labuladong.滑动窗口;

import java.util.HashMap;
import java.util.Map;

/**
 * @Auther: qingle
 * @Date: 2024/10/25-3:07
 * @Description:
 * @version: 1.0
 */
public class LC3_无重复字符的最长子串 {
	public static int lengthOfLongestSubstring(String s) {
		// 初始化需要的字符和窗口中的字符的哈希表
//		Map<Character, Integer> need = new HashMap<>();
		Map<Character, Integer> window = new HashMap<>();
//		for (char c : t.toCharArray()) {
//			need.put(c, need.getOrDefault(c, 0) + 1);
//		}

		int left = 0, right = 0;
//		int valid = 0; // 窗口中满足条件的字符数量
//		int start = 0; // 最小覆盖子串的起始索引
//		int len = Integer.MAX_VALUE; // 最小覆盖子串的长度
		int res = 0;
		// 记录最小覆盖子串的起始索引及长度
//		int start = 0, len = Integer.MAX_VALUE;

		while (right < s.length()) {
			// c 是将移入窗口的字符
			char c = s.charAt(right);
			right++;

			// 进行窗口内数据的一系列更新
//			if (need.containsKey(c)) {
//				window.put(c, window.getOrDefault(c, 0) + 1);
//				if (window.get(c).equals(need.get(c))) {
//					valid++;
//				}
//			}
			// 进行窗口内数据的一系列更新
			window.put(c, window.getOrDefault(c, 0) + 1);
			// 判断左侧窗口是否要收缩
			while (window.get(c) > 1) {
				char d = s.charAt(left);
				left++;
				// 进行窗口内数据的一系列更新
				window.put(d, window.get(d) - 1);
			}

//			// 判断左侧窗口是否要收缩
//			while (valid == need.size()) {
//				// 在这里更新最小覆盖子串
//				if (right - left < len) {
//					start = left;
//					len = right - left;
//				}
//
//				// d 是将移出窗口的字符
//				char d = s.charAt(left);
//				left++;
//
//				// 进行窗口内数据的一系列更新
//				if (need.containsKey(d)) {
//					if (window.get(d).equals(need.get(d))) {
//						valid--;
//					}
//					window.put(d, window.get(d) - 1);
//				}
//			}
			// 更新答案
			res = Math.max(res, right - left);
		}

		// 返回最小覆盖子串
		return res;
	}


	public static void main(String[] args) {
		String s = "ADOBECODEBANC";
		String t = "ABC";
		System.out.println("Minimum window substring: " + LC76_最小覆盖子串_AI_OK.model.minWindow(s, t)); // 应输出 "BANC"
	}
}